{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 20.1 Preliminary approaches"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 20.1-1\n",
    "\n",
    "> Modify the data structures in this section to support duplicate keys."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bit vector => integer vector."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 20.1-2\n",
    "\n",
    "> Modify the data structures in this section to support keys that have associated satellite data."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Satellite area."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 20.1-3\n",
    "\n",
    "> Observe that, using the structures in this section, the way we find the successor and predecessor of a value $x$ does not depend on whether $x$ is in the set at the time. Show how to find the successor of $x$ in a binary search tree when $x$ is not stored in the tree."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For each node, if $x <= node.key$, then $node.key$ is a candidate and descend to the node's left child; otherwise do nothing and descend to the node's right child. There are at most $\\lg n$ candidates, the successor is the minimal candidate, and the method runs in $\\Theta(\\lg n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 20.1-4\n",
    "\n",
    "> Suppose that instead of superimposing a tree of degree $\\sqrt{u}$, we were to superimpose a tree of degree $u^{1/k}$, where $k > 1$ is a constant. What would be the height of such a tree, and how long would each of the operations take?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Height: $k$\n",
    "\n",
    "How long: $O(k\\sqrt{u})$"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
